动态调度——基于循环的示例
AP SHANTHI博士
该模块的目标是对一系列指令进行时钟级模拟，包括进行动态调度的分支。我们将研究数据结构如何维护相关信息以及如何处理危险。
我们首先回顾一下动态调度。动态调度是一种技术，其中硬件重新安排指令执行以减少停顿，同时保持数据流和异常行为。动态调度的优点是：
它处理在编译时依赖项未知的情况
–（例如，因为它们可能涉及内存引用）
它简化了编译器
它允许为一个管道编译的代码在不同的管道上高效运行
硬件推测，一种具有显着性能优势的技术，建立在动态调度之上
在动态调度的流水线中，所有指令按顺序通过发布阶段；然而，它们可以在第二阶段停止或相互绕过，从而进入乱序执行。指令也将无序完成。
为了允许指令乱序执行，我们需要对解码阶段做一些改变。到目前为止，我们假设在解码阶段，MIPS 流水线解码指令并从寄存器文件中读取操作数。现在，通过动态调度，我们进行了更改以启用乱序执行。解码阶段或发布阶段仅对指令进行解码并检查结构性危险。如果没有结构性危险，即预留站可用，则发出指令。之后，指令将在保留站中等待，直到相关指令产生数据，然后读取操作数。这将使我们能够按顺序发出、乱序执行和乱序完成。
整个簿记是在硬件中完成的。硬件考虑一组称为指令窗口的指令，并尝试根据操作数的可用性重新安排这些指令的执行。硬件维护每条指令的状态并决定每条指令何时从一个阶段移动到另一个阶段。动态调度程序在硬件中引入了寄存器重命名并消除了 WAW 和 WAR 危害。
在 Tomasulo 的方法中，寄存器重命名由保留站 (RS) 提供。与每个功能单元相关联，我们有几个保留站。当发出指令时，为其分配一个保留站。保留站存储有关指令的信息并缓存操作数值（如果可用）。因此，一旦操作数可用（不一定涉及寄存器文件），保留站就获取并缓冲该操作数。这有助于避免 WAR 危险。如果操作数不可用，它会存储有关提供操作数的指令的信息。重命名是通过寄存器和保留站之间的映射完成的。当一个功能单元完成其操作时，结果在结果总线上广播，称为公共数据总线 (CDB)。该值被写入适当的寄存器以及等待该数据的保留站。当两条指令要修改同一个寄存器时，只有最后一个输出更新寄存器文件，从而处理 WAW 危险。因此，寄存器说明符与保留站一起重命名，保留站可能多于寄存器。对于加载和存储操作，我们使用加载和存储缓冲区，其中包含数据和地址，并像保留站一样工作。
下面列出了动态调度程序中的三个步骤：
问题
从 FIFO 队列中获取下一条指令
如果 RS 可用，则向 RS 发出带有操作数值的指令（如果可用）
如果 RS 不可用，它将成为结构性风险并且指令停止
如果没有发出较早的指令，则不能发出后续指令
如果操作数值不可用，指令将等待操作数到达 CDB
执行
当操作数可用时，将其存储在任何等待它的保留站中
当所有操作数准备好后，发出执行指令
通过有效地址按程序顺序维护加载和存储
在按照程序顺序进行的所有分支完成之前，不允许启动执行指令
写入结果
将 CDB 上的结果写入保留站并存储缓冲区
商店必须等到收到地址和值
动态调度器维护三个数据结构——保留站、跟踪将修改寄存器的指令的寄存器结果数据结构和指令状态数据结构。第三个更多是为了理解的目的。预留站组件如下图所示：
名称 - 识别预留站
Op——在单元中执行的操作（例如，+或-）
Vj、Vk - 源操作数的值
– 存储缓冲区有 V 字段，要存储的结果
Qj、Qk——产生源寄存器的保留站（要写入的值）
– 存储缓冲区只有用于 RS 产生结果的 Qi
Busy——表示预约站或FU忙
寄存器结果状态——指示哪个功能单元将写入每个寄存器（如果存在）。当没有将写入该寄存器的未决指令时，它是空白的。指令状态给出指令窗口中每条指令的状态。
图 18.1 显示了 Tomasulo 的动态调度程序的组织结构。指令从指令队列中取出并发出。在发布阶段，指令被解码并分配一个 RS 条目。如果可用，RS 站也会缓冲操作数。否则，RS 条目在 Q 字段中标记未决 RS 值。结果通过 CDB 传递到适当的寄存器，如寄存器结果数据结构以及未决 RS 所指示。
了解了 Tomasulo 动态调度程序的基础知识后，我们现在将讨论动态调度如何针对指令序列发生。上一个模块讨论了没有分支的情况。当我们考虑执行优化时，如果只考虑基本块，那么编译器和硬件都没有太多选择。一个基本块是一个直线代码序列，除了入口处没有分支进入，除了出口处没有分支出。由于平均动态分支频率为 15% 到 25%，我们通常只有 4 到 7 条指令在一对分支之间执行。此外，基本块中的指令很可能相互依赖。因此，基本块没有为利用 ILP 提供太多空间。为了获得实质性的性能增强，我们必须跨多个基本块利用 ILP。开发并行性的最简单方法是探索循环级并行性，以开发循环迭代之间的并行性。矢量架构是处理循环级并行的一种方式。否则，我们将不得不查看利用循环级并行性的动态或静态方法。常用的方法之一是循环展开，通过硬件动态分支预测，或由编译器使用静态分支预测静态地展开。我们将不得不研究利用循环级并行性的动态或静态方法。常用的方法之一是循环展开，通过硬件动态分支预测，或由编译器使用静态分支预测静态地展开。我们将不得不研究利用循环级并行性的动态或静态方法。常用的方法之一是循环展开，通过硬件动态分支预测，或由编译器使用静态分支预测静态地展开。
This example with loops will illustrate how the hardware dynamically unrolls the loop using dynamic branch prediction. We also assume that instructions beyond the branch are fetched and issued based on the dynamic branch predictor’s prediction. However, these instructions beyond the branch are not executed till the branch is resolved. This is because of the fact that, if the branch prediction fails and we have already executed instructions and written into memory or the register file, it cannot be undone. That is, we are not speculatively executing instructions.
Let us consider the loop as shown below.
Loop: LD F0 0 R1
MULTD F4 F0 F2
SD F4 0 R1
SUBI R1 R1 #8
BNEZ R1 Loop
图 18.2 显示了所考虑的指令序列以及所维护的三种数据结构。我们将假设三个Add保留站和两个Mul保留站。还有三个加载缓冲区和三个存储缓冲区。假设 Add 的延迟为 2，Multiply 需要 4 个时钟，第一次加载需要 8 个时钟，因为 L1 缓存未命中，第二次加载需要 1 个时钟（命中）。我们将考虑循环的两次迭代。R1 寄存器初始化为 80，因此循环执行 10 次。为了模拟清楚，我们将显示整数指令 SUBI 和 BNEZ 的时钟。然而，实际上，这些整数指令将在浮点指令之前。
在第一个时钟周期内，发出 Load1。分配了一个加载缓冲区条目，它的状态现在是忙碌的，有效地址计算所需的 R1 的内容和值 0 存储在缓冲区中。寄存器结果状态显示寄存器 F0 将被 Load buffer1 标识的指令写入。
在第二个时钟周期内，Load1 从发出阶段移动到执行阶段。计算出有效地址 (0+R1) (80) 并存储在 Load buffer1 中。同时，发出指令2，即Mul1。它被分配了Mult1条目，寄存器F2的内容被取出并存储在Vk的位置。另一个操作数 F0 现在无法获取，必须等待 Load1 完成。这在 Qj 字段中表示为 Mult1。Mult1 保留站被标记为忙碌。寄存器结果状态显示寄存器 F4 将被 Mult1 标识的指令写入。
在第三个时钟周期内，发出 Store1。为该存储分配了存储缓冲区条目 Store1。有效地址计算的值 0 和 (R1) 存储在那里。此外，数据字段指示 Mult1 必须为 Store1 生成数据。请注意，Load1 存在缓存未命中且未执行内存访问。Mul1 指令需要来自 Load1 指令的数据并且也被停止。这种情况如图 18.3 所示。
在第四个时钟周期内，向整数单元发出Sub指令。Store 计算有效地址 (80) 并存储在 Store1 条目中。在第五个时钟周期内，向整数单元发出分支指令。
在第 6 个时钟周期内，假设分支预测器预测了要采取的分支，则完成循环的动态展开，并将第二次迭代的 Load2 发送到 Load2 入口。此条目标记为忙碌。寄存器结果状态显示寄存器 F0 将被 Load2 标识的指令写入。请注意，虽然我们对两个加载指令使用相同的寄存器 F0，但不会发生 WAW 危险，因为两个加载中的后一个只写入 F0。同时，Sub指令完成完成。
在第七个时钟周期，下发第二次迭代的Mul指令。它被分配了Mult2条目，寄存器F2的内容被取出并存储在Vk中。另一个操作数 F0 现在无法获取，必须等待 Load2 完成。这在 Qj 字段中表示为 Load2。Mult2 保留站被标记为忙碌。寄存器结果状态显示寄存器 F4 将被 Mult2 标识的指令写入。这覆盖了 F4 必须修改寄存器 F4 的事实，避免 WAW 危险。观察到重命名允许寄存器文件从计算中完全分离，并且第一次和第二次迭代完全重叠。Sub 指令写入其结果。Branch 是依赖于 Sub 的数据，尚未执行。因此，Load2 after Branch 不执行。
在第 8 个时钟周期内，发出 Store2。为该存储分配了存储缓冲区条目 Store2。此外，数据字段指示 Mult2 必须为 Store2 生成数据。请注意，Load1 尚未完成内存访问。Mul 指令需要来自 Load 指令的数据并且也被停止。分支指令在这个时钟周期内被解析。
在第 9 个时钟周期，Load2 和 Store2 的有效地址计算发生。同时，Load1 完成执行（延迟 7 – 时钟周期 3-9）并发出第二次迭代的 Sub。第 10 个时钟周期将 Load1 结果写入 CDB，同时填充 Mult1 数据。也发出第二条分支指令。Load2 指令也在这里进行内存访问。
在第 11 个时钟周期，Mul1 开始执行，Load2 将结果写入 CDB，从而写入寄存器 F0。Sub2 完成执行。请注意，Load1 的初始加载值永远不会写入 F0。Load2 已经为 Mult2 生成了数据，因此 Mul2 指令现在可以执行了。Load3 在这个时钟周期内发出。
在第十二个时钟周期内，Mul2 开始执行，Sub2 写入其结果。由于存在结构性危险（没有 Mult 保留站），因此无法发出第三条 Mul 指令。第二个分支在第十三时钟周期得到解决。Mul1 指令在第十四个时钟周期内完成，Mul2 指令在第十五个时钟周期内完成执行。Mul1 将结果写入 15，Mul2 将结果写入 16。因此，Store1 在 16 时完成，Store2 在 17 时完成。只有在第16个时钟周期才能发出Mul3，其他指令才能在随后的时钟周期发出。最终的时间表如图 18.4 所示。
观察是否存在有序问题、无序执行和无序完成。由于重命名过程，多次迭代对寄存器使用不同的物理目的地（动态循环展开）。这就是为什么 Tomasulo 的方法能够重叠循环的多次迭代。保留站允许指令发出提前通过整数控制流操作。它们缓冲寄存器的旧值，从而完全避免否则会发生的 WAR 停顿。因此我们可以说 Tomasulo 的方法动态地构建了数据流依赖图。然而，性能提升取决于分支预测的准确性。如果分支预测出错，则必须丢弃从错误路径获取和发出的指令，从而导致惩罚。
Tomasulo 的动态调度方式的优点如下：
(1) 危害检测逻辑的分布：
– Tomasulo 的方法使用分布式保留站和 CDB
– 如果多条指令在等待一个结果，并且每条指令都有其他操作数，则可以通过在 CDB 上广播的方式同时释放指令
– 如果使用集中式寄存器文件，则当寄存器总线可用时，单元必须从寄存器中读取其结果。
(2) 消除WAW和WAR危害的失速
– 保留站中操作数的缓冲，一旦它们变得可用，就在寄存器和保留站之间进行映射。此重命名过程可避免 WAR 危险。即使后续指令修改寄存器文件，也没有问题，因为操作数已经被读取和缓冲。
– 当两条或更多条指令写入同一个寄存器时，导致WAW危险，寄存器结果状态中只保留最新的寄存器信息。这种重命名避免了 WAW 危险。
然而，这种方法并非没有缺点。以下是缺点：
复杂
o 记账完成后硬件变得复杂，CDB 和关联比较
许多关联商店 (CDB) 高速运行
性能受限于公共数据总线
o 每个 CDB 必须转到多个功能单元。这导致高电容和高布线密度
o 只有一个 CDB，每个周期可以完成的功能单元数量限制为一个！
多个 CDB 将导致并行关联存储的更多 FU 逻辑
非精确中断！
o 乱序执行会导致不精确的中断。我们将在稍后讨论投机时讨论这个问题。
我们还没有讨论与内存位置相关的问题。他们也必须得到妥善处理。只要它们访问不同的地址，加载和存储就可以安全地无序完成。如果加载和存储访问相同的地址，则
加载在程序顺序存储之前，交换它们会导致 WAR 危害，或
存储在程序顺序中的加载之前，交换它们会导致 RAW 危害。
类似地，将两个商店交换到同一地址，会导致 WAW 危险。因此，为了确定是否可以在给定时间执行加载，处理器可以检查在程序顺序中加载之前的任何未完成存储是否与加载共享相同的数据存储器地址。类似地，存储必须等到没有未执行的加载或程序顺序较早的存储并共享相同的数据存储器地址。
总而言之，我们已经查看了一个带有分支的动态调度示例，其中硬件在运行时对代码进行动态重组。根据分支预测，动态展开分支。分支之外的指令被提取并发出，但不执行。已经详细说明了在每个时钟周期内完成的簿记和执行的各个步骤。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A. Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。